부산대학교자료구조
Scientific Inference Lab

When Do We Visit the Root

Depth First Tree Traversals

트리 순회는 트리의 모든 노드를 정해진 순서로 한 번씩 방문하는 절차다. 전위 순회, 중위 순회, 후위 순회는 자식 노드를 왼쪽부터 처리하되 루트를 두 부분 트리보다 먼저, 사이에, 나중에 처리하는 위치만 다르다.

전위 순회(preorder traversal)루트 → 왼쪽 → 오른쪽 순서다.
중위 순회(inorder traversal)왼쪽 → 루트 → 오른쪽 순서다.
후위 순회(postorder traversal)왼쪽 → 오른쪽 → 루트 순서다.

visit 문장의 위치가 방문 순서를 바꾼다

같은 트리에서 순회 방식을 바꾸면 재귀 함수의 visit 문장 위치와 출력 순서가 바뀐다. 방문 횟수를 옮기면 그때까지 처리한 노드와 방금 처리한 노드가 표시된다.

재귀 순회의 방문 순서트리와 출력 순서
트리에서 초록으로 채운 원이 방금 처리한 노드, 옅은 파란 원이 이미 처리한 노드이고 원 위 수가 처리 순서다. 아래 칸은 출력 순서다. 오른쪽 코드에서 초록 칸이 visit 문장의 위치다.

      

      

    

  


  

    
명시적 스택은 오른쪽 자식 노드를 먼저 push해 전위 순회를 만든다
stack = [A]에서 시작해 pop한 노드를 방문하고 오른쪽, 왼쪽 자식 노드 순서로 push한다. pop 횟수를 옮기면 방문한 노드와 스택의 내용이 바뀐다.

    

      

      
명시적 스택 전위 순회방문한 노드와 스택
왼쪽 트리에서 초록으로 채운 원이 방금 pop해 방문한 노드, 옅은 파란 원이 이미 방문한 노드, 점선 테두리 원이 스택에서 기다리는 노드다. 오른쪽 기둥이 스택이며 위가 맨 위다.

      

      

    

  


  

    
순회 시간은 노드 수에, 추가 공간은 높이에 달려 있다
노드 수와 트리 모양을 바꾸면 방문 횟수와, 가장 깊은 노드를 처리하는 순간 동시에 열려 있는 재귀 호출 수가 바뀐다.

    

      

        

        

      

      
호출 깊이가장 깊은 노드까지 열린 호출
초록 굵은 경로가 루트에서 가장 깊은 노드까지다. 이 노드를 처리하는 동안 경로 위 노드마다 호출 하나가 끝나지 않고 기다린다. 오른쪽 기둥은 그 순간의 호출 스택이다.